package String;//给定字符串列表 strs ，返回 它们中 最长的特殊序列 。如果最长特殊序列不存在，返回 -1 。
//
// 最长特殊序列 定义如下：该序列为某字符串 独有的最长子序列（即不能是其他字符串的子序列）。 
//
// s 的 子序列可以通过删去字符串 s 中的某些字符实现。 
//
// 
// 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括
//"aebdc"、 "aeb" 和 "" (空字符串)。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入: strs = ["aba","cdc","eae"]
//输出: 3
// 
//
// 示例 2: 
//
// 
//输入: strs = ["aaa","aaa","aa"]
//输出: -1
// 
//
// 
//
// 提示: 
//
// 
// 2 <= strs.length <= 50 
// 1 <= strs[i].length <= 10 
// strs[i] 只包含小写英文字母 
// 
// Related Topics 数组 哈希表 双指针 字符串 排序 👍 92 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class findLUSlengthII {

    //双指针判断 字符串y是不是字符串x的子序列
    private boolean checkSub(String x, String y){
        //遍历字符串y的每一个字符，i负责遍历字符串y,j负责遍历字符串x,当二者字符相等，j指针右移
        int j=0;
        for(int i=0;i<y.length() && j<x.length();i++){
            if(x.charAt(j)==y.charAt(i)){
                j++;
            }
        }
        return j == x.length();

    }
    public int findLUSlength(String[] strs) {
        int len = strs.length;  //len >= 2
        //特例
        if(len < 2){
            return -1;
        }
        //按照长度对数组中的字符串排序
        Arrays.sort(strs, (o1, o2)->o2.length()-o1.length());
        //这是字符串列表长度长的在前，遍历所有的字符串，让其它的所有字符串比较它是不是当前字符串的子序列
        //依次使用序列中的每个字符串与其他字符串比较，如果不存在其它字符串是当前字符串的子序列，说明当前字符串是特殊序列，则返回当前字符串的长度
        for (int i = 0; i < len; i++) {
            int j;
            boolean flag = true;
            for(j=0;j<len;j++){
                if(i==j){
                    continue;
                }
                if(checkSub(strs[i],strs[j])){
                    //找到第一个不满足
                    flag = false;
                    break;
                }
            }
            if(flag){
                return strs[i].length();
            }
        }
        return -1;


    }
}
//leetcode submit region end(Prohibit modification and deletion)
